#include "stand.h"

extern int a[];



//可把递归看成循环中的一次.循环指定的一堆数据,然后将循环好的数据交有栈的上一级使用.
//递归是现将少数数据排列完毕后,再将多数数据整合.
void quick_sort(int a[],int ac) 
{
	int pivot;
	int *container;


	/* base case */
	if (ac <= 2) return;

	pivot= ac /2;
	/* recusion */
	quick_sort(a,pivot);

	container = malloc(sizeof(int) *ac); //申请内存空间


	int i,j,k;
	
	i=0;
	j=0;
	while (i<ac) {
		if (a[i] >= a[pivot]) {
//			container[i] = a[i]; //上面的两个数是否需要交换位置呢?
			swap(a+i,a+pivot);
		}else {
			swap(a+pivot,a+i);
		}
	}

	for (i=0;i<ac;i++) {
		a[i] = container[i];
	}

	free(container);
		
}


void quick_sort2 (int a[],int ac) 
{
	int pivot;
	int sample;

	swap(a+0,a+ac/2);
	pivot = 1; //说好的取中间的值,怎么变成1了?

	/* test each element */
	for (sample = 1; sample < ac ; sample++) {
		if (a[sample] < a[0]) {
			swap(a+pivot,a+sample);
			pivot ++;
		}
	}

	/* swap an element (which <= pavlue) with a[0] */
	swap(a+0,a+pivot-1);

	/* base case, if only tow elements are in the array,
	 * the above pass has already sorted the array
	 * */
	if (ac <= 2) return;
	else {
		/* recursion */
		quick_sort2(a,pivot);
		quick_sort2(a+pivot,ac-pivot);
	}



}

void quick_sort3(int a [],int ac) //抛弃
{

	int pivot = ac/2;
	printf("[%d,%d]\n",pivot,a[pivot]);


	swap(a+0,a+pivot);//将基准值与0下标做一下替换.方便下面判断  //问题的所在.你只可以去当前数组中的第一个作为替换值,但不一定的a+0   最好可以将部分数组的长度和部分数组在整个数组中所在的位置.  使用a+0不靠谱.
	pivot = 1;//pivot=1,将小于a[0]的值放到1~ac之间.

	int i;
	for (i=1;i<ac;i++) {
		if (a[0] >= a[i]) {
			swap(a+pivot,a+i);//将小值放在数组的前面
			pivot++;
		}else {
			;//什么也不需要做,因为,上面既然已经将小的全部移动到左边了,那剩下的就是最大的了.
		}
	}

	swap(a+0,a+pivot-1);//再将基准数再调换回来
	print_arr(a,ac);
	printf("pivot is :%d\n",pivot);


	/* recursion */
	if (ac <= 2) return ; //递归存在问题,执行一次是没有问题的.
	else {
		quick_sort3(a,pivot);//最小值的数组
		quick_sort3(a+pivot,ac-pivot);
	}
}

int adjustArray(int s[], int l ,int r)
{
	int i=l, j=r;
	int x = s[l];
	while (i < j) {
		
		while (i < j && s[j] >= x) {
			j--;
		}
		if (i < j) {
			s[i] = s[j];
			i++;
		}


		while(i<j && s[i] < x) {
			i++;
		}
		if (i<j) {
			s[j] = s[i];
			j--;
		}
	}

	s[i] = x;

	return i;
}

void quick_sort4(int s[],int l,int r)
{
	if (l < r) {
		int i = adjustArray(s,l,r);
		quick_sort4(s,l,i-l);
		quick_sort4(s,i+1,r);
	}
}

int main()
{
	int ac = ARRLEN(a,ac);
	print_arr(a,ac);

	quick_sort4(a,ac/2,ac);
	print_arr(a,ac);
}

